package com.song.algorithm.collections;

import java.util.NoSuchElementException;

/**
 * @desc: 双向链表的简单实现
 * @author: WUSONG
 * @date: 2018/10/26 0026下午 3:13
 */
public class DoubleLinkedList<E> {

    private Node head;

    private Node tail;

    private int size;

    public DoubleLinkedList() {
        this.size = 0;
    }

    private class Node{
        E element;
        Node prev;
        Node next;

        public Node(E element, Node prev, Node next) {
            this.element = element;
            this.prev = prev;
            this.next = next;
        }
    }

    public int size(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void addFirst(E element){
        Node newNode = new Node(element, null, this.head);
        if (head != null){
            head.prev = newNode;
        }
        this.head = newNode;
        if (tail == null){
            this.tail = newNode;
        }
        size++;
    }

    public void addLast(E element){
        Node newNode = new Node(element, this.tail, null);
        if (tail != null){
            tail.next = newNode;
        }
        this.tail = newNode;
        if (head == null){
            this.head = newNode;
        }
        size++;
    }

    public E removeFirst(){
        if (size == 0){
            throw new NoSuchElementException();
        }
        Node tmp = this.head;
        Node newHead = this.head.next;
        if (newHead != null){
            newHead.prev = null;
        }
        this.head = newHead;
        size--;
        return tmp.element;
    }

    /**
     * 向前循环（从head到tail）
     */
    public void iterateForward(){
        if (head == null){
            return;
        }
        Node tmp = head;
        while (tmp != null){
            System.out.print(tmp.element + " ");
            tmp = tmp.next;
        }
        System.out.println();
    }

    /**
     * 向后循环（从tail向head）
     */
    public void iterateBackward(){
        if (tail == null){
            return;
        }
        Node tmp = tail;
        while (tmp != null){
            System.out.print(tmp.element + " ");
            tmp = tmp.prev;
        }
        System.out.println();
    }
}
